Apple Developer Connection 1998 Fall: Game Toolkit/Disc.iso/SDKs/Apple Game Sprockets/InputSprocket/Sample Drivers/Common Driver Code/ListUtils.c

C/C++ Source or Header | 1998-07-14 | 11.2 KB | 575 lines | [TEXT/CWIE]

/*************************************************************************************

File:      ListUtils.c

Copyright © 1996, 1997, 1998 Apple Computer, Inc., All Rights Reserved


You may incorporate this sample code into your applications without
restriction, though the sample code has been provided "AS IS" and the
responsibility for its operation is 100% yours.  However, what you are
not permitted to do is to redistribute the source as "DSC Sample Code"
after having made changes. If you're going to re-distribute the source,
we require that you make it clear in the source that the code was
descended from Apple Sample Code, but that you've made changes.

*************************************************************************************/

#include <Memory.h>
#include <string.h>

#include "ListUtils.h"

#if !__cplusplus && !__MWERKS__
#define inline
#endif

/*
************************************************************************
** inline functions
************************************************************************
*/
inline void *
MemAlloc( UInt32 inSize )
{
    return NewPtrClear( inSize );
}

inline void
MemFree( void *inPtr)
{
    DisposePtr( inPtr );
}

/*
************************************************************************
**
** Name: List_New
**
** Description:
**
**    Allocate a new list.
**
************************************************************************
*/
List *
List_New( void )
{
    List *theList;

    theList = MemAlloc( sizeof( List ) );

    return theList;
}

/*
************************************************************************
**
** Name: List_Dispose
**
** Description:
**
**    Dispose of a list.  Will dispose of all list nodes that are still
**    present in the list.
**
************************************************************************
*/
void
List_Dispose(
    List *inList
)
{
    ListNode *theNode;

    /* empty the list of any nodes */
    while( List_GetHead( inList ) )
    {
        theNode = List_RemoveHead( inList );
        List_DisposeNode( theNode );
    }

    /* delete the list */
    MemFree( inList );
}

/*
************************************************************************
**
** Name: List_Initialize
**
** Description:
**
**    Initialize list members.
**
************************************************************************
*/
void List_Initialize(
    List *inList
)
{
    inList->head =
    inList->tail =
    inList->curr = NULL;

    inList->iterationDirection = 0;
}

/*
************************************************************************
**
** Name: List_NewNode
**
** Description:
**
**    Allocate a new list node and optionally place it at the head or
**    tail of the list.
**
************************************************************************
*/
ListNode *
List_NewNode(
    List *inList,
    ListNodeAddLocation inAddLocation
)
{
    ListNode *theNode;

    theNode = MemAlloc( sizeof( ListNode ) );
    if( theNode )
    {
        if( kListAddTail == inAddLocation )
            List_AddTail( inList, theNode );
        else if( kListAddHead == inAddLocation )
            List_AddHead( inList, theNode );
    }

    return theNode;
}

/*
************************************************************************
**
** Name: List_DisposeNode
**
** Description:
**
**    Dispose of a list node.
**
************************************************************************
*/
void
List_DisposeNode(
    ListNode *inNode
)
{
    MemFree( inNode );
}

/*
************************************************************************
**
** Name: List_GetHead
**
** Description:
**
**    Return the node at the list head.
**
************************************************************************
*/
ListNode *
List_GetHead(
    List *inList
)
{
    return inList->head;
}

/*
************************************************************************
**
** Name: List_GetTail
**
** Description:
**
**    Return the node at the list tail.
**
************************************************************************
*/
ListNode *
List_GetTail(
    List *inList
)
{
    return inList->tail;
}

/*
************************************************************************
**
** Name: List_AddToHead
**
** Description:
**
**    Add a list node to the list head.
**
************************************************************************
*/
void
List_AddHead(
    List *inList,
    ListNode *inNode
)
{
    /* link in node */
    inNode->next = inList->head;
    inNode->prev = NULL;

    /* adjust head */
    if( inList->head )
        inList->head->prev = inNode;
    inList->head = inNode;

    /* adjust tail */
    if( NULL == inList->tail )
        inList->tail = inNode;
}

/*
************************************************************************
**
** Name: List_AddToTail
**
** Description:
**
**    Add a list node to the list tail.
**
************************************************************************
*/
void
List_AddTail(
    List *inList,
    ListNode *inNode
)
{
    /* link in node */
    inNode->next = NULL;
    inNode->prev = inList->tail;

    /* adjust tail */
    if( inList->tail )
        inList->tail->next = inNode;
    inList->tail = inNode;

    /* adjust head */
    if( NULL == inList->head )
        inList->head = inNode;
}

/*
************************************************************************
**
** Name: List_RemoveHead
**
** Description:
**
**    Remove the list head node.
**
************************************************************************
*/
void *
List_RemoveHead(
    List *inList
)
{
    void *theData = NULL;
    ListNode *theNode;

    theNode = inList->head;
    if( theNode )
    {
        /* move to next node if this is the current one */
        if( inList->iterationDirection && ( inList->curr == theNode ) )
            List_Iterate( inList );

        /* remove head */
        inList->head = theNode->next;
        if( inList->head )
            inList->head->prev = NULL;

        /* check tail */
        if( inList->tail == theNode )
            inList->tail = NULL;

        theData = theNode->data;
        List_DisposeNode( theNode );
    }

    return theData;
}

/*
************************************************************************
**
** Name: List_RemoveTail
**
** Description:
**
**    Remove the list tail node.
**
************************************************************************
*/
void *
List_RemoveTail(
    List *inList
)
{
    void *theData = NULL;
    ListNode *theNode;

    theNode = inList->tail;
    if( theNode )
    {
        /* move to next node if this is the current one */
        if( inList->iterationDirection && ( inList->curr == theNode ) )
            List_Iterate( inList );

        /* remove tail */
        inList->tail = theNode->prev;
        if( inList->tail )
            inList->tail->next = NULL;

        /* check head */
        if( inList->head == theNode )
            inList->head = NULL;

        theData = theNode->data;
        List_DisposeNode( theNode );
    }

    return theData;
}

/*
************************************************************************
**
** Name: List_RemoveNode
**
** Description:
**
**    Find the node in the list and remove it.
**
************************************************************************
*/
void *
List_RemoveNode(
    List *inList,
    ListNode *inNode
)
{
    void *theData = NULL;
    ListNode *theNode;

    /* check head & tail */
    if( inList->head == inNode )
        return List_RemoveHead( inList );
    else if( inList->tail == inNode )
        return List_RemoveTail( inList );

    theNode = inList->head->next;
    while( theNode )
    {
        if( theNode == inNode )
        {
            /* move to next node if this is the current one */
            if( inList->iterationDirection && ( inList->curr == theNode ) )
                List_Iterate( inList );

            /* adjust links */
            if( theNode->prev )
                theNode->prev->next = theNode->next;
            if( theNode->next )
                theNode->next->prev = theNode->prev;

            theData = theNode->data;
            List_DisposeNode( theNode );

            break;
        }

        theNode = theNode->next;
    }

    return theData;
}

/*
************************************************************************
**
** Name: List_RemoveNodeByData
**
** Description:
**
**    Find the node in the list with the specified data and remove it.
**
************************************************************************
*/
void *
List_RemoveNodeByData(
    List *inList,
    void *inNodeData
)
{
    void *theData = NULL;
    ListNode *theNode;

    /* check head & tail */
    if( inList->head->data == inNodeData )
        return List_RemoveHead( inList );
    else if( inList->tail->data == inNodeData )
        return List_RemoveTail( inList );

    theNode = inList->head->next;
    while( theNode )
    {
        if( theNode->data == inNodeData )
        {
            /* move to next node if this is the current one */
            if( inList->iterationDirection && ( inList->curr == theNode ) )
                List_Iterate( inList );

            /* adjust links */
            if( theNode->prev )
                theNode->prev->next = theNode->next;
            if( theNode->next )
                theNode->next->prev = theNode->prev;

            theData = theNode->data;
            List_DisposeNode( theNode );

            break;
        }

        theNode = theNode->next;
    }

    return theData;
}

/*
************************************************************************
**
** Name: List_GetIterationState
**
** Description:
**
**    Returns the iteration state of a list.  Useful to see if the list
**    is already being iterated over.
**
************************************************************************
*/
ListIterationDirection
List_GetIterationState(
    List *inList
)
{
    return inList->iterationDirection;
}

/*
************************************************************************
**
** Name: List_BeginIteration
**
** Description:
**
**    Begin iteration over a list.  Will optionally block if the
**    list is already being iterated over.
**
************************************************************************
*/
Boolean
List_BeginIteration(
    List *inList,
    ListIterationDirection inIterateDirection,
    Boolean inBlockWhileBusyFlag
)
{
    if( inBlockWhileBusyFlag )
    {
        while( List_GetIterationState( inList ) )
            /* empty body */;
    }
#if 0
    // So, here's the problem:  If the inBlockWhileBusyFlag is true
    // then you can never have nested traversals of this list.  However,
    // if the block isn't preserved somehow then we're not thread safe.
    // So, until someone figures out a way to take care of this we're
    // just removing this clause and nested traversals will have the
    // blocking flag set to false.
    else if( inList->iterationDirection )
    {
        return false;
    }
#endif
    inList->iterationDirection = inIterateDirection;

    if( kListIterateForward == inIterateDirection )
        inList->curr = inList->head;
    else if( kListIterateBackward == inIterateDirection )
        inList->curr = inList->tail;

    return true;
}

/*
************************************************************************
**
** Name: List_EndIteration
**
** Description:
**
**    End iteration over a list, allowing others to access the list.
**
************************************************************************
*/
void
List_EndIteration(
    List *inList
)
{
    inList->iterationDirection = kListNotIterating;
}

/*
************************************************************************
**
** Name: List_Iterate
**
** Description:
**
**    Get the list node data for the current node, and move to the next
**    node in the iteration direction.
**
************************************************************************
*/
void *
List_Iterate(
    List *inList
)
{
    void *theData = NULL;

    if( inList->curr )
    {
        theData = inList->curr->data;

        if( kListIterateForward == inList->iterationDirection )
            inList->curr = inList->curr->next;
        else if( kListIterateBackward == inList->iterationDirection )
            inList->curr = inList->curr->prev;
        else
            inList->curr = NULL;
    }

    return theData;
}